1. Field of Invention
The present invention relates to the field of network communications. In particular, the present invention describes improved duplicate message detection.
2. Description of Related Art
In most computer networks, information is communicated using messages. Nodes on the network prepare messages and transmit these messages to other nodes. Each message contains a number of bytes corresponding to the information to be communicated and a number of bytes identifying the message, called the header. These types of networks can be used in control systems. For example, a control system network can be used to control the heating and the ventilation of a large building.
A sender node can request that a receiver node return an acknowledgment. An acknowledgment is a message that is in response to another message. If such a request is made, the sender node will wait for the acknowledgment. If no acknowledgment is received the sender node can then transmit a duplicate of the original message. However, this raises the problem of distinguishing between original messages and duplicate messages. For reliable communications, the receiver should detect that a given message is a duplicate, and the sender node should detect whether a given acknowledgment is a duplicate. The following illustrates an example of the undesirable effects that lack of a duplicate message detection system can have. Assume that the sender node transmits a command to open a valve 10% more. The receiver receives and executes the command. Assume that the acknowledgment from the receiver node has been lost. The sender node would not know that the original message had been received and would then transmit the open valve 10% more command. If the receiver node does not detect this second message as a duplicate, the valve will be opened 20%. Clearly, this could be disastrous.
One previous method of detecting duplicate messages is to use transaction identifiers (transaction ids). A transaction is the start to end process of successfully communicating a message. The transaction id identifies each separate transaction. Transaction ids are also referred to as transaction sequence numbers. A sender node includes a transaction id in each original message. The receiver node remembers this transaction id. If a subsequent message arrives with exactly the same transaction id, then the receiver node knows that the message has been previously received. The receiver node can ignore the command contained in the message. The receiver node also know that it must transmit the acknowledgment. The receiver node includes the transaction id in the acknowledgment. The sender node, upon receipt of the acknowledgment, can end the transaction.
One practical problem with the use of transaction ids is that they can only represent a limited range. That is, after a certain number of transactions, transaction ids must be reused. The set of all possible transaction ids is called the transaction space. Generally, if the receiver node receives two messages with the same transaction id, the receiver node will assume that the second message is a duplicate. To prevent the receiver node from erroneously assuming a second message with a previously used transaction id is a duplicate, previous systems use timers to allow received messages, and their transaction ids, to expire. The receiver node uses a transaction timer for each transaction id.
In Tanenbaum, A. N., Computer Networks, 2nd Edition, at page 429, a large transaction space (e.g. 2.sup.32 -1) is defined for use in local and wide area networks. This helps to ensure that when transaction ids start repeating, a sufficient period of time has passed for all previous transactions to have expired. In typical local and wide area networks, the data rates are relatively high, and the number of messages are relatively large. Therefore, using a large number of bits to represent the transaction id in a message is an acceptable design constraint. For example, a transaction id may be only four bytes of a message containing two kilobytes of information.
However, some networks have relatively low data rates and relatively small sized messages. For example, in a networked control system, data rates may be 600 baud. For example, temperature information may only be a few bytes of data. Therefore, requiring a large number of bits to represent the transaction id is unacceptable. One previous system uses a transaction space of sixteen transaction ids. After initiating sixteen transactions, the first node reuses the transaction ids. If, for example, one node is used for configuring many other nodes on the network, then it is quite possible to reuse a transaction id that has not yet expired. This can cause the receiver node to erroneously disregard the information in the second message. LONBUILDER 2.2, available from Echelon Systems of Palo Alto, Calif., supports such a network and communications system.
What is needed is a method and apparatus having improved duplicate message detection, but have an acceptable ratio between the size of the header and the rest of the information to be communicated.
An improved method and apparatus for detecting duplicate messages.